package ArraySecond.SwordOfferItem;

import java.util.HashMap;

public class Array10_new {
    /**
     * 剑指 Offer II 010. 和为 k 的子数组
     * 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
     * <p>
     * <p>
     * <p>
     * 示例 1 :
     * <p>
     * 输入:nums = [1,1,1], k = 2
     * 输出: 2
     * 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
     * 示例 2 :
     * <p>
     * 输入:nums = [1,2,3], k = 3
     * 输出: 2
     */

    public static int subarraySum(int[] nums, int k) {
//        int sum = 0;
//        int slow = 0;
//        int fast = 0;
//        int count = 0;
//        for (fast = 0; fast < nums.length; fast++) {
//            sum += nums[fast];
//            while (sum >= k && slow <= fast) {
//                if (sum == k) {
//                    count++;
//                }
//                sum -= nums[slow++];
//            }
//        }
//        return count;
        int count = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        int pre_sum = 0;
        for (int i = 0; i < nums.length; i++) {
            pre_sum += nums[i];
            count += hashMap.getOrDefault(pre_sum - k, 0);
            hashMap.put(pre_sum, hashMap.getOrDefault(pre_sum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(subarraySum(new int[]{1, 1, 0, 1}, 2));
    }
}
